package dp;

/**
 * @author Liaorun
 */
public class ScrambleString {

    public static void main(String[] args) {
        String test1 = "abcd";
        String test2 = "cdab";
        System.out.println(isScramable1(test1, test2));
        System.out.println(dpCheck(test1, test2));

        test2 = "cadb";
        System.out.println(isScramable1(test1, test2));
        System.out.println(dpCheck(test1, test2));

    }

    /**
     * 两个字符串是否长度一样 && 每个元素的数量一样
     * exampe: abc cba  -> true
     * abb  abc -> false
     *
     * @param str1
     * @param str2
     * @return
     */
    public static boolean sameTypeSameNumber(char[] str1, char[] str2) {
        if (str1.length != str2.length) {
            return false;
        }

        int[] map = new int[256];

        for (int i = 0; i < str1.length; i++) {
            map[str1[i]]++;
        }

        for (int i = 0; i < str2.length; i++) {
            if (--map[str2[i]] < 0) {
                return false;
            }
        }

        return true;
    }


    public static boolean isScramable1(String s1, String s2) {
        if ((s1 == null && s2 != null) || (s1 != null && s2 == null)) {
            return false;
        }

        if (s1 == null && s2 == null) {
            return true;
        }

        if (s1.equals(s2)) {
            return true;
        }

        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();

        if (!sameTypeSameNumber(str1, str2)) {
            return false;
        }

        int N = s1.length();

        return process(str1, str2, 0, 0, N);
    }

    /**
     * 返回str1[从l1开始往右长度为size的子串] 和 str2[从l2开始往右长度为size的子串]是否互为旋变串
     * 在str1中的这一段和str2中的这一段一定是等长的，所以只用一个参数size
     *
     * @param str1
     * @param str2
     * @param l1
     * @param l2
     * @param size
     * @return
     */
    private static boolean process(char[] str1, char[] str2, int l1, int l2, int size) {

        if (size == 1) {
            return str1[l1] == str2[l2];
        }

        // 枚举每一种情况，有一个计算出互为旋变串就返回true,都算不出来最后返回false
        for (int leftPart = 1; leftPart < size; leftPart++) {
            // str1: 左1 右1
            // str2: 左2 右2
            if (process(str1, str2, l1, l2, leftPart) && (process(str1, str2, l1 + leftPart, l2 + leftPart, size - leftPart))) {
                // (左1和左2互为旋变串） && （左1和左2互为旋变串）
                return true;
            } else if (process(str1, str2, l1, l2 + size - leftPart, leftPart) && (process(str1, str2, l1 + leftPart, l2, size - leftPart))) {
                // (左1和右2互为旋变串） && （右1和左2互为旋变串）
                return true;
            }
        }

        return false;
    }


    public static boolean dpCheck(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();

        int N = str1.length;

        boolean[][][] dp = new boolean[N][N][N + 1];

        for (int l1 = 0; l1 < N; l1++) {
            for (int l2 = 0; l2 < N; l2++) {
                // 立方体最底下的一层
                dp[l1][l2][1] = (str1[l1] == str2[l2]);
            }
        }


        // 从第二层的位置向上填，一直填到第N层
        for (int size = 2; size <= N; size++) {
            // 本层的东西，不互相依赖
            // 任何一个dp[i][j][size] 都依赖dp[...][...][k] (k < size)(它下面层的数据）
            for (int l1 = 0; l1 <= N - size; l1++) {
                for (int l2 = 0; l2 <= N - size; l2++) {

                    for (int leftPart = 1; leftPart < size; leftPart++) {

                        // str1: 左1 右1
                        // str2: 左2 右2
                        // (左1和左2互为旋变串） && （左1和左2互为旋变串）
                        if (dp[l1][l2][leftPart] && dp[l1 + leftPart][l2 + leftPart][size - leftPart]) {
                            dp[l1][l2][size] = true;
                            break;
                            // (左1和右2互为旋变串） && （右1和左2互为旋变串）
                        } else if (dp[l1][l2 + size - leftPart][leftPart] && dp[l1 + leftPart][l2][size - leftPart]) {
                            dp[l1][l2][size] = true;
                            break;
                        }
                    }
                }
            }
        }

        return dp[0][0][N];
    }
}
